package com.googlecode.gaal.analysis.impl;

import com.googlecode.gaal.analysis.api.IntervalSetBuilder;
import com.googlecode.gaal.data.api.IntervalSet;
import com.googlecode.gaal.data.impl.IntervalBitSet;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree.BinaryNode;
import com.googlecode.gaal.suffix.api.SuffixArray;

public class LocalMaximumSetBuilder implements IntervalSetBuilder {

    @Override
    public <E extends BinaryNode<E>, T extends SuffixArray & BinaryIntervalTree<E>> IntervalSet<E> buildIntervalSet(
            T tree) {
        IntervalSet<E> maximalSet = new IntervalBitSet<E>(tree);
        traverse(maximalSet, tree.top(), 0);
        return maximalSet;
    }

    private <E extends BinaryNode<E>> int traverse(IntervalSet<E> maximalSet, E interval, int parentLcp) {
        if (!interval.isTerminal()) {
            int lcp = interval.lcp();
            int leftLcp = traverse(maximalSet, interval.leftChild(), lcp);
            int rightLcp = traverse(maximalSet, interval.rightChild(), lcp);
            if (leftLcp != -1 && leftLcp == rightLcp) {
                if (parentLcp != lcp) {
                    maximalSet.add(interval);
                    return -1;
                }
                return lcp;
            } else {
                return -1;
            }
        } else {
            return parentLcp;
        }
    }
}
